#ifndef ANT_H
#define ANT_H

#endif // ANT_H

#pragma once
//#include "rectangle.h"
#include "utils.h"
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include "data.h"
#include "pheromone_map.h"
#include <algorithm>
#include<time.h>
#include<vector>
#include<map>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
#include<ctime>
#include <fstream>
#include <string>

#define N 999
float P = 0.85;//衰减因子
float Q = 1;//学习因子
float RAN1 = 0;//0不用蚁群
float RAN2 = 0;
using namespace std;
bool strict_weak_ordering(const pair<int, float> a, const pair<int, float> b)
{
    return a.second > b.second;
}

class ant {

public:
    //每只蚂蚁含有一个存放矩形vector，同一批次的蚂蚁初始化的矩形vector相同，但经历每次摆放后vector不同
    vector<rectangle*> rt_v;

    //等待拼接矩形队列
    vector<rectangle*> rt_q;

    //记录第一个放的矩形
    int root_index;

    //用矩形vector初始化一只蚂蚁
    int Time = 0;

    int result_area;
    int area = 0;
    int set_area()
    {
        for (int i = 0; i < rt_v.size() / 2; i++)
        {
            area += rt_v[i]->get_occu_area();
        }

        return area;
    }
    vector<int> finish_index;
    ant(vector<rectangle*> rt_v_)
    {
        for (int i = 0; i < rt_v_.size(); i++)
        {
            rectangle *r2 = rt_v_[i]->get_copy();
            rt_v.push_back(r2);
        }
        set_area();
    }

    ~ant()
    {
        for(int i = 0; i < rt_v.size() / 2; i++)
        {
            delete rt_v[i];
        }

    }

    //矩形碰撞检测算法
    bool Rectangle_collision_detection(rectangle rt)
    {
        for (int i = 0; i < finish_index.size(); i++)
        {
            if (rt_v[finish_index[i]]->index == rt.index)
                continue;
            rectangle red = *rt_v[finish_index[i]];
            rectangle blue = rt;

            if (
                abs(red.x_mid - blue.x_mid) < red.width / 2.0 + blue.width / 2.0 //横向判断
                &&
                abs(red.y_mid - blue.y_mid) < red.height / 2.0 + blue.height / 2.0 //纵向判断
                )
            {

                return false;//碰撞
            }
        }
        return true;//不碰撞
    }



    //随机决策函数,critical_value是随机界限
    bool static stochastic_decision01(float critical_value)
    {
        //产生0-1随机数
//        float num;
//        int i;
        float random;
        srand(time(NULL));
        random = rand() % (N + 1) / (float)(N + 1);

        if (random > critical_value)
            return false;
        else
            return true;
    }

    //产生0-（n-1）的随机整数
    //如果stochastic_decision01决策为false，调用此函数
    int stochastic_decision0n(int n)
    {
        float num;
        static int i;
        float random;
        srand(((unsigned int)(time(NULL) + i)));
        random = (rand() % n);
        i += 311;
        return int(random);
    }

    //vector打乱顺序算法
    vector<int> STLLuanXu(vector<int> vec)
    {
        static int i = 0;
        //乱序算法
        srand((unsigned int)(time(NULL) + i));
        random_shuffle(vec.begin(), vec.end());
        i += 311;
        return vec;
    }

    //返回第一步矩形下标
    int first_step(bool first)
    {
        //float critical_value = 0.8;

        //蚁群最优决策
        if (stochastic_decision01(RAN1) && !first)
        {
            int max = 0;
            int index_f;
            for (int i = 0; i < rt_v.size(); i++)
            {
                if (peromone_map[i][i] >= max)
                {
                    max = peromone_map[i][i];
                    index_f = i;
                }
            }
            root_index = index_f;


            finish_index.push_back(root_index);
            return root_index;
        }

        //随机决策
        else
        {
            int random_index = stochastic_decision0n(rt_v.size());
            //cout << "第一步随机决策" << random_index << endl;
            root_index = random_index;
            finish_index.push_back(root_index);
            return random_index;
        }

    }

    //摆放第一个矩形 更新该矩形位置信息和flag
    void set_first_rctangle()
    {
        (*rt_v[root_index]).x1 = 0;
        (*rt_v[root_index]).y1 = 0;
        (*rt_v[root_index]).x2 = (*rt_v[root_index]).x1 + (*rt_v[root_index]).width;
        (*rt_v[root_index]).y2 = (*rt_v[root_index]).y1 + (*rt_v[root_index]).height;

        (*rt_v[root_index]).x_mid = ((*rt_v[root_index]).x1 + (*rt_v[root_index]).x2) / 2;
        (*rt_v[root_index]).y_mid = ((*rt_v[root_index]).y1 + (*rt_v[root_index]).y2) / 2;

        (*rt_v[root_index]).flag = true;

        //把转置矩形flag也置true
        if (root_index >= rt_v.size() / 2)
            rt_v[root_index - rt_v.size() / 2]->flag = true;
        else
            rt_v[root_index + rt_v.size() / 2]->flag = true;
        //将第一步摆放的矩形加入队列
        rt_q.push_back(rt_v[root_index]);
        Time += 2;
    }

    //新蚁群拼法
    void select_next_rctangle1(bool first)
    {
        int result;
        int map_type = 0;//区分两个表
        int x;//横坐标
        int y;//纵坐标
        int num_now;
        int max = 0;
        //cout << rt_q.size() << endl;
        for (int i = 0; i < rt_q.size(); i++)
        {
            //cout << i << endl;
            //1表竖着看
            for (int j = 0; j < rt_v.size(); j++)
            {
                if (peromone_map[j][rt_q[i]->index] >= max)
                {
                    if (!rt_v[j]->flag)//B没放过
                    {
                        //cout << "B";
                        if (!rt_q[i]->up)//A上面没被放过
                        {
                            //cout << "C";
                            rt_v[j]->set_up(rt_q[i]);
                            if (Rectangle_collision_detection(*rt_v[j]))//不碰撞
                            {
                                //cout << "D";
                                max = peromone_map[j][rt_q[i]->index];
                                map_type = 1;
                                x = j;
                                y = rt_q[i]->index;
                                num_now = i;
                            }
                        }
                    }
                }
            }


            //2表横着看
            for (int j = 0; j < rt_v.size(); j++)
            {
                if (peromone_map2[rt_q[i]->index][j] >= max)
                    if (!rt_v[j]->flag)//B没放过
                        if (!rt_q[i]->right)//A右面没被放过
                        {
                            rt_v[j]->set_right(rt_q[i]);
                            if (Rectangle_collision_detection(*rt_v[j]))//不碰撞
                            {
                                max = peromone_map2[rt_q[i]->index][j];
                                map_type = 2;
                                x = rt_q[i]->index;
                                y = j;
                                num_now = i;
                            }
                        }
            }

        }

        if (map_type == 1)//x放在y上
        {
            //cout << "选中" << endl;
            finish_index.push_back(x);
            result = x;
            rt_v[x]->flag = true;
            Time += 2;
            if (x >= rt_v.size() / 2)
                rt_v[x - rt_v.size() / 2]->flag = true;
            else
                rt_v[x + rt_v.size() / 2]->flag = true;
            rt_q.push_back(rt_v[x]);
            rt_v[y]->r_left = rt_v[x];//改左子树
            rt_v[y]->up = true;
            //cout << "蚁群往A" << y << "上放 B index" << x << endl;
            if (rt_v[y]->up&&rt_v[y]->right)
                rt_q.erase(rt_q.begin() + num_now);//y是随机选中的当前矩形
        }
        if (map_type == 2)//y放在x右
        {
            //cout << "选中" << endl;
            finish_index.push_back(y);
            result = y;
            rt_v[y]->flag = true;
            Time += 2;
            if (y >= rt_v.size() / 2)
                rt_v[y - rt_v.size() / 2]->flag = true;
            else
                rt_v[y + rt_v.size() / 2]->flag = true;
            rt_q.push_back(rt_v[y]);
            rt_v[x]->r_right = rt_v[y];//改右子树
            rt_v[x]->right = true;
            //cout << "蚁群往A" << x << "右放 B index" << y << endl;
            if (rt_v[x]->up&&rt_v[x]->right)
                rt_q.erase(rt_q.begin() + num_now);//y是随机选中的当前矩形
        }
    }

    void select_next_rctangle(bool first,const int& area_sum)
    {
        int result;

        //从rt_q中随机选中的当前矩形下标
        int num_now;
        //随机从队列中
        //cout << "队列大小 " << rt_q.size()<<endl;
        num_now = select_by_probability(rt_q);
        //1、取出选中矩形
        //2、查看上是否摆放

        //3、队首矩形上部未摆放

        //对角线右,优先往上拼
        if (rt_q[num_now]->x2 > rt_q[num_now]->y2) {
            if (!(rt_q[num_now])->up)
            {
                //找矩形往上部放
                vector<int> record;
                //随机决策
                if ((!stochastic_decision01(RAN2)) || first)
                {
                    //cout << "随机" << endl;
                    for (int j = 0; j < rt_v.size(); j++)
                    {
                        record.push_back(j);
                    }
                    vector<int> v = STLLuanXu(record);

                    for (int j = 0; j < v.size(); j++)
                    {
                        //i是B矩形的index
                        int i = v[j];

                        if ((!(rt_v[i])->flag))
                        {
                            rt_v[i]->set_up(rt_q[num_now]);
                            if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                            {
                                finish_index.push_back(rt_v[i]->index);
                                //成功选取B
                                result = i;//选取的矩形下标
                                //cout << "随机往A "<<rt_q[num_now]->index<<"上放 B index" << result << endl;
                                rt_v[i]->flag = true;
                                Time += 2;//包含转置矩形

                                //i的转置矩形flag视为true
                                if (i >= rt_v.size() / 2)
                                    rt_v[i - rt_v.size() / 2]->flag = true;
                                else
                                    rt_v[i + rt_v.size() / 2]->flag = true;

                                rt_q.push_back(rt_v[i]);
                                rt_q[num_now]->r_left = rt_v[i];//改左子树

                                break;
                            }

                        }
                    }
                    rt_q[num_now]->up = true;
                }

                else
                {
                    //蚁群决策
                    //信息素表纵向遍历队首的rt_q[num_now]->index列
                    int index;//

                    //将该列排序
                    vector<pair<int, float>> vec;
                    //for (int i = 0; i < rt_v.size(); i++)
                    for (int i = 0; i < rt_q[num_now]->index; i++)
                    {
                        vec.push_back(make_pair(i, peromone_map3[i][rt_q[num_now]->index]));
                    }
                    sort(vec.begin(), vec.end(), strict_weak_ordering);//降序

                    for (vector<pair<int, float>>::iterator it = vec.begin(); it != vec.end(); it++)
                    {
                        int i = it->first;
                        //cout << it->first << " " << it->second << endl;

                        //选出的矩形没有被放过+不碰撞就停止
                        if (!(rt_v[i]->flag))
                        {
                            rt_v[i]->set_up(rt_q[num_now]);
                            if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                            {
                                finish_index.push_back(rt_v[i]->index);
                                result = i;//选取的矩形下标
                                rt_v[i]->flag = true;
                                Time += 2;//包含转置矩形
                                //i的转置矩形flag视为true

                                if (i >= rt_v.size() / 2)
                                    rt_v[i - rt_v.size() / 2]->flag = true;
                                else
                                    rt_v[i + rt_v.size() / 2]->flag = true;

                                rt_q.push_back(rt_v[i]);
                                rt_q[num_now]->r_left = rt_v[i];//改左子树
                                //cout << "蚁群往A " << rt_q[num_now]->index << "上放 B index" << result << endl;
                                //print_map(rt_v.size());
                                break;
                            }
                        }
                    }
                    rt_q[num_now]->up = true;
                }
            }


            //3、队首矩形上部已摆放
            else
            {
                vector<int> record;
                //队首矩形右部未摆放
                if (!rt_q[num_now]->right)
                {
                    //随机决策
                    if ((!stochastic_decision01(RAN2)) || first)
                    {
                        //cout << "尝试随机决策" << endl;
                        vector<int> record;
                        for (int j = 0; j < rt_v.size(); j++)
                        {
                            record.push_back(j);
                        }
                        vector<int> v = STLLuanXu(record);
                        for (int j = 0; j < rt_v.size(); j++)
                        {
                            int i = v[j];
                            //B没有被放过+不碰撞就停止
                            if ((!(rt_v[i])->flag))
                            {
                                rt_v[i]->set_right(rt_q[num_now]);//这里

                                if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                                {
                                    finish_index.push_back(rt_v[i]->index);
                                    //cout << "没碰撞" << endl;
                                    result = i;
                                    rt_v[i]->flag = true;
                                    Time += 2;//包含转置矩形

                                    //i的转置矩形flag视为true
                                    if (i >= rt_v.size() / 2)
                                        rt_v[i - rt_v.size() / 2]->flag = true;
                                    else
                                        rt_v[i + rt_v.size() / 2]->flag = true;

                                    rt_q[num_now]->r_right = rt_v[i];//改右子树
                                    //cout << "随机往A"<< rt_q[num_now]->index <<"右放 B index" << result << endl;
                                    rt_q.push_back(rt_v[i]);

                                    if (!Rectangle_collision_detection(*rt_v[i]))
                                    {
                                        cout << "**********************右部放完发现" << rt_v[i]->index << "存在碰撞" << "检测所有矩形坐标**********************" << endl;
                                        for (int k = 0; k < rt_v.size(); k++) {
                                            rt_v[k]->to_String();
                                        }
                                        cout << "断电" << endl;
                                    }

                                    break;
                                }
                            }
                        }
                        rt_q[num_now]->right = true;

                    }

                    //蚁群决策
                    else
                    {
                        int index;
                        vector<pair<int, float> > vec;
                        //for (int i = 0; i < rt_v.size(); i++)
                        for (int i = 0; i < rt_q[num_now]->index; i++)
                        {
                            //将该行排序
                            vec.push_back(make_pair(i, peromone_map3[rt_q[num_now]->index][i]));
                        }
                        sort(vec.begin(), vec.end(), strict_weak_ordering);//降序

                        for (vector<pair<int, float>>::iterator it = vec.begin(); it != vec.end(); it++)
                        {
                            int i = it->first;
                            //cout << it->first << " " << it->second << endl;

                            //随机选出的矩形没有被放过+和num_now矩形不是同一个矩形（翻转）+不碰撞就停止
                            if (!(rt_v[i]->flag))
                            {
                                rt_v[i]->set_right(rt_q[num_now]);
                                if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                                {
                                    finish_index.push_back(rt_v[i]->index);
                                    result = i;//选取的矩形下标
                                    rt_v[i]->flag = true;
                                    Time += 2;//包含转置矩形
                                    //i的转置矩形flag视为true

                                    if (i >= rt_v.size() / 2)
                                        rt_v[i - rt_v.size() / 2]->flag = true;
                                    else
                                        rt_v[i + rt_v.size() / 2]->flag = true;

                                    rt_q.push_back(rt_v[i]);
                                    rt_q[num_now]->r_right = rt_v[i];//改右子树
                                    //cout << "蚁群往A" << rt_q[num_now]->index << "右放 B index" << result << endl;
                                    print_map(rt_v.size());
                                    break;
                                }
                            }
                        }
                        rt_q[num_now]->right = true;
                        //上右都摆放的矩形出队
                    }
                    rt_q.erase(rt_q.begin() + num_now);//num_now是随机选中的当前矩形
                }

                //队首矩形右部已摆放(上右都摆放完)
                //该矩形出列

            }
            //未完成：摆放完但是没有set矩形类 只获得下标
        }
        //对角线上，优先往右拼
        else{
        //如果右边可以拼
            if (!(rt_q[num_now])->right)
            {
                //找矩形往右部放
                vector<int> record;
                //随机决策
                if ((!stochastic_decision01(RAN2)) || first)//0.4蚁群
                {
                    //cout << "随机" << endl;
                    for (int j = 0; j < rt_v.size(); j++)
                    {
                        record.push_back(j);
                    }
                    vector<int> v = STLLuanXu(record);

                    for (int j = 0; j < v.size(); j++)
                    {
                        //i是B矩形的index
                        int i = v[j];

                        if ((!(rt_v[i])->flag))
                        {
                            rt_v[i]->set_right(rt_q[num_now]);
                            if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                            {
                                finish_index.push_back(rt_v[i]->index);
                                //成功选取B
                                result = i;//选取的矩形下标
                                //cout << "随机往A "<<rt_q[num_now]->index<<"上放 B index" << result << endl;
                                rt_v[i]->flag = true;
                                Time += 2;//包含转置矩形

                                //i的转置矩形flag视为true
                                if (i >= rt_v.size() / 2)
                                    rt_v[i - rt_v.size() / 2]->flag = true;
                                else
                                    rt_v[i + rt_v.size() / 2]->flag = true;

                                rt_q.push_back(rt_v[i]);

                                //这里有问题

                                rt_q[num_now]->r_right = rt_v[i];//改左子树

                                break;
                            }

                        }
                    }
                    rt_q[num_now]->right = true;
                }

                else
                {
                    //蚁群决策
                    //信息素表纵向遍历队首的rt_q[num_now]->index列
                    int index;//

                    //将该列排序
                    vector<pair<int, float>> vec;
                    //for (int i = 0; i < rt_v.size(); i++)
                    for (int i = 0; i < rt_q[num_now]->index; i++)
                    {
                        vec.push_back(make_pair(i, peromone_map3[i][rt_q[num_now]->index]));
                    }
                    sort(vec.begin(), vec.end(), strict_weak_ordering);//降序

                    for (vector<pair<int, float>>::iterator it = vec.begin(); it != vec.end(); it++)
                    {
                        int i = it->first;
                        //cout << it->first << " " << it->second << endl;

                        //选出的矩形没有被放过+不碰撞就停止
                        if (!(rt_v[i]->flag))
                        {
                            rt_v[i]->set_right(rt_q[num_now]);
                            if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                            {
                                finish_index.push_back(rt_v[i]->index);
                                result = i;//选取的矩形下标
                                rt_v[i]->flag = true;
                                Time += 2;//包含转置矩形
                                //i的转置矩形flag视为true

                                if (i >= rt_v.size() / 2)
                                    rt_v[i - rt_v.size() / 2]->flag = true;
                                else
                                    rt_v[i + rt_v.size() / 2]->flag = true;

                                rt_q.push_back(rt_v[i]);
                                rt_q[num_now]->r_right = rt_v[i];//改右子树
                                //cout << "蚁群往A " << rt_q[num_now]->index << "上放 B index" << result << endl;
                                print_map(rt_v.size());
                                break;
                            }
                        }
                    }
                    rt_q[num_now]->right = true;
                }
            }

            //3、队首矩形右部已摆放
            //往上拼
            else
            {
                vector<int> record;
                //队首矩形右部未摆放
                if (!rt_q[num_now]->up)
                {
                    //随机决策
                    if ((!stochastic_decision01(RAN2)) || first)
                    {
                        //cout << "尝试随机决策" << endl;
                        vector<int> record;
                        for (int j = 0; j < rt_v.size(); j++)
                        {
                            record.push_back(j);
                        }
                        vector<int> v = STLLuanXu(record);
                        for (int j = 0; j < rt_v.size(); j++)
                        {
                            int i = v[j];
                            //B没有被放过+不碰撞就停止
                            if ((!(rt_v[i])->flag))
                            {
                                rt_v[i]->set_up(rt_q[num_now]);//这里

                                if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                                {
                                    finish_index.push_back(rt_v[i]->index);
                                    //cout << "没碰撞" << endl;
                                    result = i;
                                    rt_v[i]->flag = true;
                                    Time += 2;//包含转置矩形

                                    //i的转置矩形flag视为true
                                    if (i >= rt_v.size() / 2)
                                        rt_v[i - rt_v.size() / 2]->flag = true;
                                    else
                                        rt_v[i + rt_v.size() / 2]->flag = true;

                                    //这里有问题

                                    rt_q[num_now]->r_left = rt_v[i];//改右子树
                                    //cout << "随机往A"<< rt_q[num_now]->index <<"右放 B index" << result << endl;
                                    rt_q.push_back(rt_v[i]);

                                    if (!Rectangle_collision_detection(*rt_v[i]))
                                    {
                                        cout << "**********************右部放完发现" << rt_v[i]->index << "存在碰撞" << "检测所有矩形坐标**********************" << endl;
                                        for (int k = 0; k < rt_v.size(); k++) {
                                            rt_v[k]->to_String();
                                        }
                                        cout << "overlap1" << endl;
                                    }

                                    break;
                                }
                            }
                        }
                        rt_q[num_now]->up = true;

                    }

                    //蚁群决策

                    else
                    {
                        int index;
                        vector<pair<int, float> > vec;
                        //for (int i = 0; i < rt_v.size(); i++)
                        for (int i = 0; i < rt_q[num_now]->index; i++)
                        {
                            //将该行排序
                            vec.push_back(make_pair(i, peromone_map3[rt_q[num_now]->index][i]));
                        }
                        sort(vec.begin(), vec.end(), strict_weak_ordering);//降序

                        for (vector<pair<int, float>>::iterator it = vec.begin(); it != vec.end(); it++)
                        {
                            int i = it->first;
                            //cout << it->first << " " << it->second << endl;

                            //随机选出的矩形没有被放过+和num_now矩形不是同一个矩形（翻转）+不碰撞就停止
                            if (!(rt_v[i]->flag))
                            {
                                rt_v[i]->set_up(rt_q[num_now]);
                                if (Rectangle_collision_detection(*rt_v[i]))//检测不碰撞
                                {
                                    finish_index.push_back(rt_v[i]->index);
                                    result = i;//选取的矩形下标
                                    rt_v[i]->flag = true;
                                    Time += 2;//包含转置矩形
                                    //i的转置矩形flag视为true

                                    if (i >= rt_v.size() / 2)
                                        rt_v[i - rt_v.size() / 2]->flag = true;
                                    else
                                        rt_v[i + rt_v.size() / 2]->flag = true;

                                    rt_q.push_back(rt_v[i]);
                                    rt_q[num_now]->r_left = rt_v[i];//改左子树
                                    //cout << "蚁群往A" << rt_q[num_now]->index << "右放 B index" << result << endl;
                                    //print_map(rt_v.size());
                                    break;
                                }
                            }
                        }
                        rt_q[num_now]->up = true;
                        //上右都摆放的矩形出队
                    }
                    rt_q.erase(rt_q.begin() + num_now);//num_now是随机选中的当前矩形

                }

                //队首矩形右部已摆放(上右都摆放完)
                //该矩形出列

            }
        }
    }

    //广度优先遍历
    int breadthFirstSearch() {
        int max_x = 0;
        int max_y = 0;
        rectangle *root = rt_v[root_index];
        queue<rectangle *> nodeQueue;  //使用C++的STL标准模板库
        nodeQueue.push(root);
        rectangle *node;
        while (!nodeQueue.empty()) {
            node = nodeQueue.front();
            //碰撞检测（关闭）
            if (!Rectangle_collision_detection(*node))
            {
                //cout << "**********************右部放完发现" << node->index << "存在碰撞" << "检测所有矩形坐标**********************" << endl;
                for (int k = 0; k < rt_v.size(); k++) {
                    rt_v[k]->to_String();
                }
                cout << "overlap" << endl;
            }

            if (node->x2 >= max_x)
                max_x = node->x2;
            if (node->y2 >= max_y)
                max_y = node->y2;
            nodeQueue.pop();

            if (node->r_left) {
                //cout << node->index << "左子树是" << node->r_left->index << endl;
                nodeQueue.push(node->r_left);  //先将左子树入队
            }
            if (node->r_right) {
                //cout << node->index << "右子树是" << node->r_right->index << endl;
                nodeQueue.push(node->r_right);  //再将右子树入队
            }
        }
        //返回该拼接的面积
        result_area = max_x * max_y;
        return max_x * max_y;
    }

    //广度优先遍历更新全局信息素
    void bfs_updata_map()
    {
        for (int i = 0; i < rt_v.size(); i++)
        {
            for (int j = 0; j < rt_v.size(); j++)
            {
                peromone_map[i][j] *= P;
            }
        }
        rectangle *root = rt_v[root_index];
        peromone_map[root->index][root_index] += Q * float(area) / float(result_area);//对角线信息素更新
        //peromone_map[root->index][root_index] += Q /(1- (float(area) / float(result_area)));//对角线信息素更新
        queue<rectangle *> nodeQueue;  //使用C++的STL标准模板库
        nodeQueue.push(root);
        rectangle *node;
        while (!nodeQueue.empty()) {
            node = nodeQueue.front();
            nodeQueue.pop();

            if (node->r_left) {
                peromone_map[node->r_left->index][node->index] += Q * float(area) / float(result_area);//信息素更新node->index列node->r_left->index行
                //peromone_map[node->r_left->index][node->index] += Q /(1- (float(area) / float(result_area)));//信息素更新node->index列node->r_left->index行

                nodeQueue.push(node->r_left);  //先将左子树入队
            }
            if (node->r_right) {
                peromone_map2[node->r_right->index][node->index] += Q * float(area) / float(result_area);//更新node->index列node->r_right->index行
                //peromone_map2[node->r_right->index][node->index] += Q /(1-( float(area) / float(result_area)));//更新node->index列node->r_right->index行
                nodeQueue.push(node->r_right);  //再将右子树入队
            }
        }

    }
};
